package com.lun.swordtowardoffer2.c14;

public class FindTargetSumWays {

	public int findTargetSumWays(int[] nums, int S) {
		int sum = 0;
		
		for(int num : nums) {
			sum += num;
		}
		
		if(((sum + S) & 1) == 1 || S > sum) {
			return 0;
		}
		
		return subsetSum(nums, (sum + S) / 2);
	}

	private int subsetSum(int[] nums, int target) {
		int[] dp = new int[target + 1];
		
		dp[0] = 1;
		
		for(int num : nums) {
			for(int j = target; j >= num; --j) {
				dp[j] += dp[j - num];
			}
		}
		
		return dp[target];
	}
	
	
}
